/*
 * $Id$
 * 
 * See the end of this file for a copyright notice.
 */

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <stddef.h>
#include <limits.h>
#include <setjmp.h>

#include "ngram.h"

#define LOGFILE "ngram.out"
#define LOGFILE_ENV "NGRAM_LOG"

/*
 * except
 */

typedef struct {
	char           *reason;
} Except_T;

typedef struct Except_Frame Except_Frame;

struct Except_Frame {
	Except_Frame   *prev;
	jmp_buf         env;
	const char     *file;
	int             line;
	const Except_T *exception;
};

enum {
	Except_entered = 0, Except_raised,
	Except_handled, Except_finalized
};

static Except_Frame *Except_stack;

#if UNUSED
static const Except_T Assert_Failed;
#endif

static void     Except_raise(const Except_T * e, const char *file, int line);

#define RAISE(e) Except_raise(&(e), __FILE__, __LINE__)
#define RERAISE Except_raise(Except_frame.exception, \
	Except_frame.file, Except_frame.line)
#define RETURN switch (Except_stack = Except_stack->prev,0) default: return
#define TRY do { \
	volatile int Except_flag; \
	Except_Frame Except_frame; \
	Except_frame.prev = Except_stack; \
	Except_stack = &Except_frame;  \
	Except_flag = setjmp(Except_frame.env); \
	if (Except_flag == Except_entered) {
#define EXCEPT(e) \
		if (Except_flag == Except_entered) Except_stack = Except_stack->prev; \
	} else if (Except_frame.exception == &(e)) { \
		Except_flag = Except_handled;
#define ELSE \
		if (Except_flag == Except_entered) Except_stack = Except_stack->prev; \
	} else { \
		Except_flag = Except_handled;
#define FINALLY \
		if (Except_flag == Except_entered) Except_stack = Except_stack->prev; \
	} { \
		if (Except_flag == Except_entered) \
			Except_flag = Except_finalized;
#define END_TRY \
		if (Except_flag == Except_entered) Except_stack = Except_stack->prev; \
		} if (Except_flag == Except_raised) RERAISE; \
} while (0)

static Except_Frame *Except_stack = NULL;

static void 
Except_raise(const Except_T * e, const char *file, int line)
{
	Except_Frame   *p = Except_stack;
	assert(e);
	if (p == NULL) {
		fprintf(stderr, "Uncaught exception");
		if (e->reason)
			fprintf(stderr, " %s", e->reason);
		else
			fprintf(stderr, " at 0x%p", e);
		if (file && line > 0)
			fprintf(stderr, " raised at %s:%d\n", file, line);
		fprintf(stderr, "aborting...\n");
		fflush(stderr);
		abort();
	}
	p->exception = e;
	p->file = file;
	p->line = line;
	Except_stack = Except_stack->prev;
	longjmp(p->env, Except_raised);
}

/*
 * mem
 */


#if UNUSED
static void    *Mem_calloc(long count, long nbytes, const char *file, int line);
static void    *Mem_resize(void *ptr, long nbytes, const char *file, int line);
#endif

static const    Except_T Mem_Failed;
static void    *Mem_alloc(long nbytes, const char *file, int line);
static void     Mem_free(void *ptr, const char *file, int line);

#define ALLOC(nbytes) \
	Mem_alloc((nbytes), __FILE__, __LINE__)
#define CALLOC(count, nbytes) \
	Mem_calloc((count), (nbytes), __FILE__, __LINE__)
#define  NEW(p) ((p) = ALLOC((long)sizeof *(p)))
#define NEW0(p) ((p) = CALLOC(1, (long)sizeof *(p)))
#define FREE(ptr) ((void)(Mem_free((ptr), \
	__FILE__, __LINE__), (ptr) = 0))
#define RESIZE(ptr, nbytes) 	((ptr) = Mem_resize((ptr), \
	(nbytes), __FILE__, __LINE__))


static const Except_T Mem_Failed = {"Allocation Failed"};
static void *
Mem_alloc(long nbytes, const char *file, int line)
{
	void           *ptr;
	assert(nbytes > 0);
	ptr = malloc(nbytes);
	if (ptr == NULL) {
		if (file == NULL)
			RAISE(Mem_Failed);
		else
			Except_raise(&Mem_Failed, file, line);
	}
	return ptr;
}

#if UNUSED
static void *
Mem_calloc(long count, long nbytes, const char *file, int line)
{
	void           *ptr;
	assert(count > 0);
	assert(nbytes > 0);
	ptr = calloc(count, nbytes);
	if (ptr == NULL) {
		if (file == NULL)
			RAISE(Mem_Failed);
		else
			Except_raise(&Mem_Failed, file, line);
	}
	return ptr;
}

static void    *
Mem_resize(void *ptr, long nbytes, const char *file, int line)
{
	assert(ptr);
	assert(nbytes > 0);
	ptr = realloc(ptr, nbytes);
	if (ptr == NULL) {
		if (file == NULL)
			RAISE(Mem_Failed);
		else
			Except_raise(&Mem_Failed, file, line);
	}
	return ptr;
}
#endif

static void 
Mem_free(void *ptr, const char *file, int line)
{
	if (ptr)
		free(ptr);
}

/*
 * atoms
 */


#if UNUSED
static int         Atom_length(const char *str);
static const char *Atom_int(long n);
#endif
static const char *Atom_new(const char *str, int len);
static const char *Atom_string(const char *str);

#define NELEMS(x) ((sizeof (x))/(sizeof ((x)[0])))
static struct atom {
	struct atom    *link;
	int             len;
	char           *str;
}              *buckets[2048];
static unsigned long scatter[] = {
	2078917053, 143302914, 1027100827, 1953210302, 755253631, 2002600785,
	1405390230, 45248011, 1099951567, 433832350, 2018585307, 438263339,
	813528929, 1703199216, 618906479, 573714703, 766270699, 275680090,
	1510320440, 1583583926, 1723401032, 1965443329, 1098183682, 1636505764,
	980071615, 1011597961, 643279273, 1315461275, 157584038, 1069844923,
	471560540, 89017443, 1213147837, 1498661368, 2042227746, 1968401469,
	1353778505, 1300134328, 2013649480, 306246424, 1733966678, 1884751139,
	744509763, 400011959, 1440466707, 1363416242, 973726663, 59253759,
	1639096332, 336563455, 1642837685, 1215013716, 154523136, 593537720,
	704035832, 1134594751, 1605135681, 1347315106, 302572379, 1762719719,
	269676381, 774132919, 1851737163, 1482824219, 125310639, 1746481261,
	1303742040, 1479089144, 899131941, 1169907872, 1785335569, 485614972,
	907175364, 382361684, 885626931, 200158423, 1745777927, 1859353594,
	259412182, 1237390611, 48433401, 1902249868, 304920680, 202956538,
	348303940, 1008956512, 1337551289, 1953439621, 208787970, 1640123668,
	1568675693, 478464352, 266772940, 1272929208, 1961288571, 392083579,
	871926821, 1117546963, 1871172724, 1771058762, 139971187, 1509024645,
	109190086, 1047146551, 1891386329, 994817018, 1247304975, 1489680608,
	706686964, 1506717157, 579587572, 755120366, 1261483377, 884508252,
	958076904, 1609787317, 1893464764, 148144545, 1415743291, 2102252735,
	1788268214, 836935336, 433233439, 2055041154, 2109864544, 247038362,
	299641085, 834307717, 1364585325, 23330161, 457882831, 1504556512,
	1532354806, 567072918, 404219416, 1276257488, 1561889936, 1651524391,
	618454448, 121093252, 1010757900, 1198042020, 876213618, 124757630,
	2082550272, 1834290522, 1734544947, 1828531389, 1982435068, 1002804590,
	1783300476, 1623219634, 1839739926, 69050267, 1530777140, 1802120822,
	316088629, 1830418225, 488944891, 1680673954, 1853748387, 946827723,
	1037746818, 1238619545, 1513900641, 1441966234, 367393385, 928306929,
	946006977, 985847834, 1049400181, 1956764878, 36406206, 1925613800,
	2081522508, 2118956479, 1612420674, 1668583807, 1800004220, 1447372094,
	523904750, 1435821048, 923108080, 216161028, 1504871315, 306401572,
	2018281851, 1820959944, 2136819798, 359743094, 1354150250, 1843084537,
	1306570817, 244413420, 934220434, 672987810, 1686379655, 1301613820,
	1601294739, 484902984, 139978006, 503211273, 294184214, 176384212,
	281341425, 228223074, 147857043, 1893762099, 1896806882, 1947861263,
	1193650546, 273227984, 1236198663, 2116758626, 489389012, 593586330,
	275676551, 360187215, 267062626, 265012701, 719930310, 1621212876,
	2108097238, 2026501127, 1865626297, 894834024, 552005290, 1404522304,
	48964196, 5816381, 1889425288, 188942202, 509027654, 36125855,
	365326415, 790369079, 264348929, 513183458, 536647531, 13672163,
	313561074, 1730298077, 286900147, 1549759737, 1699573055, 776289160,
	2143346068, 1975249606, 1136476375, 262925046, 92778659, 1856406685,
	1884137923, 53392249, 1735424165, 1602280572
};
static const char *
Atom_string(const char *str)
{
	assert(str);
	return Atom_new(str, strlen(str));
}

#if UNUSED
static const char *
Atom_int(long n)
{
	char            str[43];
	char           *s = str + sizeof str;
	unsigned long   m;
	if (n == LONG_MIN)
		m = LONG_MAX + 1 UL;
	else if (n < 0)
		m = -n;
	else
		m = n;
	do
		*--s = m % 10 + '0';
	while ((m /= 10) > 0);
	if (n < 0)
		*--s = '-';
	return Atom_new(s, (str + sizeof str) - s);
}
#endif
static const char *
Atom_new(const char *str, int len)
{
	unsigned long   h;
	int             i;
	struct atom    *p;
	assert(str);
	assert(len >= 0);
	for (h = 0, i = 0; i < len; i++)
		h = (h << 1) + scatter[(unsigned char) str[i]];
	h &= NELEMS(buckets) - 1;
	for (p = buckets[h]; p; p = p->link)
		if (len == p->len) {
			for (i = 0; i < len && p->str[i] == str[i];)
				i++;
			if (i == len)
				return p->str;
		}
	p = ALLOC(sizeof(*p) + len + 1);
	p->len = len;
	p->str = (char *) (p + 1);
	if (len > 0)
		memcpy(p->str, str, len);
	p->str[len] = '\0';
	p->link = buckets[h];
	buckets[h] = p;
	return p->str;
}
#if UNUSED
static int 
Atom_length(const char *str)
{
	struct atom    *p;
	int             i;
	assert(str);
	for (i = 0; i < NELEMS(buckets); i++)
		for (p = buckets[i]; p; p = p->link)
			if (p->str == str)
				return p->len;
	assert(0);
	return 0;
}
#endif

/*
 * table
 */

typedef struct {
	int             size;
	int             (*cmp) (const void *x, const void *y);
	unsigned        (*hash) (const void *key);
	int             length;
	unsigned        timestamp;
	struct binding {
		struct binding *link;
		const void     *key;
		void           *value;
	}             **buckets;
}              *T;

typedef T       Table_T;

static T 
Table_new(int hint, int cmp(const void *x, const void *y),
	  unsigned hash(const void *key));
static void     Table_free(T * table);
static void    *Table_put(T table, const void *key,
				                  void *value);
static void    *Table_get(T table, const void *key);
static void   **Table_toArray(T table, void *end);

#if UNUSED
static int      Table_length(T table);
static void    *Table_remove(T table, const void *key);
static void     Table_map(T table,
static void     apply(const void *key, void **value, void *cl), void *cl);
#endif

static int      cmpatom(const void *x, const void *y)
{
	return x != y;
}

static unsigned hashatom(const void *key)
{
	return (unsigned long) key >> 2;
}
static T 
Table_new(int hint,
	  int cmp(const void *x, const void *y),
	  unsigned hash(const void *key))
{
	T               table;
	int             i;
	static int      primes[] = {509, 509, 1021, 2053, 4093,
	8191, 16381, 32771, 65521, INT_MAX};
	assert(hint >= 0);
	for (i = 1; primes[i] < hint; i++);
	table = ALLOC(sizeof(*table) +
		      primes[i - 1] * sizeof(table->buckets[0]));
	table->size = primes[i - 1];
	table->cmp = cmp ? cmp : cmpatom;
	table->hash = hash ? hash : hashatom;
	table->buckets = (struct binding **) (table + 1);
	for (i = 0; i < table->size; i++)
		table->buckets[i] = NULL;
	table->length = 0;
	table->timestamp = 0;
	return table;
}

static void  *
Table_get(T table, const void *key)
{
	int             i;
	struct binding *p;
	assert(table);
	assert(key);
	i = (*table->hash) (key) % table->size;
	for (p = table->buckets[i]; p; p = p->link)
		if ((*table->cmp) (key, p->key) == 0)
			break;
	return p ? p->value : NULL;
}

static void    *
Table_put(T table, const void *key, void *value)
{
	int             i;
	struct binding *p;
	void           *prev;
	assert(table);
	assert(key);
	i = (*table->hash) (key) % table->size;
	for (p = table->buckets[i]; p; p = p->link)
		if ((*table->cmp) (key, p->key) == 0)
			break;
	if (p == NULL) {
		NEW(p);
		p->key = key;
		p->link = table->buckets[i];
		table->buckets[i] = p;
		table->length++;
		prev = NULL;
	} else
		prev = p->value;
	p->value = value;
	table->timestamp++;
	return prev;
}

#if UNUSED
static int 
Table_length(T table)
{
	assert(table);
	return table->length;
}
static void 
Table_map(T table,
	  void apply(const void *key, void **value, void *cl),
	  void *cl)
{
	int             i;
	unsigned        stamp;
	struct binding *p;
	assert(table);
	assert(apply);
	stamp = table->timestamp;
	for (i = 0; i < table->size; i++)
		for (p = table->buckets[i]; p; p = p->link) {
			apply(p->key, &p->value, cl);
			assert(table->timestamp == stamp);
		}
}

static void    *
Table_remove(T table, const void *key)
{
	int             i;
	struct binding **pp;
	assert(table);
	assert(key);
	table->timestamp++;
	i = (*table->hash) (key) % table->size;
	for (pp = &table->buckets[i]; *pp; pp = &(*pp)->link)
		if ((*table->cmp) (key, (*pp)->key) == 0) {
			struct binding *p = *pp;
			void           *value = p->value;
			*pp = p->link;
			FREE(p);
			table->length--;
			return value;
		}
	return NULL;
}
#endif

static void   **
Table_toArray(T table, void *end)
{
	int             i, j = 0;
	void          **array;
	struct binding *p;
	assert(table);
	array = ALLOC((2 * table->length + 1) * sizeof(*array));
	for (i = 0; i < table->size; i++)
		for (p = table->buckets[i]; p; p = p->link) {
			array[j++] = (void *) p->key;
			array[j++] = p->value;
		}
	array[j] = end;
	return array;
}

static void 
Table_free(T * table)
{
	assert(table && *table);
	if ((*table)->length > 0) {
		int             i;
		struct binding *p, *q;
		for (i = 0; i < (*table)->size; i++)
			for (p = (*table)->buckets[i]; p; p = q) {
				q = p->link;
				FREE(p);
			}
	}
	FREE(*table);
}

/*
 * ngrams
 */

#if !defined(WIDTH)
#define WIDTH 3			/* window size */
#endif

#define EXPECTED_NGRAMS 10000

typedef const char *word;

typedef struct {
	word            call[WIDTH];
}               ngram;

typedef struct {
	int             count;
	int             discovered;
}               attr;


static void     initialize(void);
static void     finalize(void);
static void     print_ngrams(Table_T tab);

/*
 * global state
 */

#if 0
static char    *cvs = "$Id$";
#endif

static char    *none = "<none>";
static int      ticks = 0;
static ngram    n;
static Table_T  ngrams = NULL;


/*
 * initialize initialize all module-global state
 */

static void 
initialize(void)
{
	int             i;
	assert(WIDTH > 0);

	for (i = 0; i < WIDTH; i++) {
		n.call[i] = none;
	}
	ngrams = Table_new(EXPECTED_NGRAMS, 0, 0);
	ticks = 0;
}

/*
 * finalize
 */

static void 
finalize(void)
{
	print_ngrams(ngrams);
	Table_free(&ngrams);
}


/*
 * emit table of all ngrams and their attributes
 */

static void 
print_ngrams(Table_T tab)
{
	int             i, j;
	attr           *a;
	ngram          *n;
	void          **array;
	FILE           *log;
	char           *logfile;

	logfile = getenv(LOGFILE_ENV);
	if (!logfile)
		logfile = LOGFILE;

	log = strcmp(logfile, "-") ? fopen(logfile, "w") : stdout;

	if (!log) {
		fprintf(stderr, "can't open logfile %s for writing\n", logfile);
		abort();
	}
	array = Table_toArray(tab, NULL);
	for (i = 0; array[i]; i += 2) {
		n = (ngram *) array[i];
		a = (attr *) array[i + 1];

		//emit ngram n with attributes a
			fprintf(log, "[%2d/%4d] ", a->count, a->discovered);
		for (j = 0; j < WIDTH; j++) {
			fprintf(log, "%-12s ", n->call[j]);
		}
		fprintf(log, "\n");
	}
	FREE(array);
	if (log != stdout)
		fclose(log);
}

/*
 * ngram_atom Record a new call and record the sequence of the last n calls
 * if it wasn't recorded already.
 */

void 
ngram_atom(const void *ptr)
{
	attr           *a;
	const char     *ngram_atom;

	if (!ngrams) {
		initialize();
		atexit(finalize);
	}
	ticks++;
	memmove(&n.call[0], &n.call[1], (WIDTH - 1) * sizeof(word));
	n.call[WIDTH - 1] = ptr;
	ngram_atom = Atom_new((char *) &n, sizeof(ngram));

	if ((a = Table_get(ngrams, ngram_atom))) {
		a->count++;
	} else {
		a = (attr *) malloc(sizeof(attr));
		assert(a);
		a->count = 1;
		a->discovered = ticks;
		Table_put(ngrams, ngram_atom, a);
	}
}

void 
ngram_string(const char *string)
{
	ngram_atom(Atom_string(string));
}


/* This module includes (slightly modified) code from 
 * "C Interfaces and Implementations: Techniques for Creating Reusable
 * Software (Addison-Wesley Professional Computing Series, 1997, ISBN
 * 0-201-49841-3) by David R. Hanson. It requires the following copyright
 * notice:
 * 
 * The author of this software is David R. Hanson.
 * 
 * Copyright (c) 1994,1995,1996,1997 by David R. Hanson. All Rights Reserved.
 * 
 * Permission to use, copy, modify, and distribute this software for any
 * purpose, subject to the provisions described below, without fee is
 * hereby granted, provided that this entire notice is included in all
 * copies of any software that is or includes a copy or modification of
 * this software and in all copies of the supporting documentation for
 * such software.
 * 
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY. IN PARTICULAR, THE AUTHOR DOES MAKE ANY REPRESENTATION OR
 * WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR
 * ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 * 
 * David Hanson / drh@microsoft.com / http://www.research.microsoft.com/~drh/
 * $Id: CPYRIGHT,v 1.2 1997/11/04 22:31:40 drh Exp $
 */

/* The other code in this module is Copyright (c) 2005 by Christian
 * Lindig <lindig@cs.uni-sb.de>, All Rights Reserved. This code is
 * distributed under the same terms as above. 
 */

